#include <vector>
#include <iostream>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        // 记录要跳过的死亡密码
        unordered_set<string> deads;
        for (string str : deadends){
            deads.insert(str);
        }
        // 记录已经穷举过的密码，不走回头路
        unordered_set<string> visited;
        queue<string> q;
        //从起点开始启动广度优先搜索
        int step = 0;
        q.push("0000");
        visited.insert("0000");

        // bfs 框架
        while (!q.empty()) {
            int sz = q.size();
            // 将当前队列所有节点向周围扩散
            for (int i = 0; i < sz; i++){
                string cur = q.front();
                q.pop();
                // 判断是否满足条件 达到终点
                if (deads.count(cur) == 1){
                    continue;
                }
                if ( cur.compare(target) == 0){
                    print_set(visited);
                    return step;
                }

                // 把一个节点未遍历节点加入队列
                for (int j = 0; j < 4; j++){
                    string up = plus_one(cur, j);
                    // cout<<"visited:"<<endl;
                    // print_set(visited);
                    // cout<<"up: "<<up<<endl;
                    if (visited.count(up) == 0){
                        q.push(up);
                        visited.insert(up);
                    }
                    string down = minus_one(cur, j);
                    // cout<<"down: "<<down<<endl;
                    if (visited.count(down) == 0){
                        q.push(down);
                        visited.insert(down);
                    }
                }

            }
            // 增加步数
            step++;
        }
        // 穷举完还未找到，那就是找不到了
        return -1;
    }

    void print_set(unordered_set<string> set){
        cout<<"set size:"<<set.size()<<endl;
        for (string str : set){
            cout << "set print: " << str << endl;
        }
    }

    // 密码数字组合 + 1
    string minus_one(string str, int j){
        string copy = str;
        if (copy[j] == '0'){
            copy[j] = '9';
        }else{
            copy[j] -= 1;
        }
        return copy;
    }
    // 密码数字组合 -1
    string plus_one(string str, int j){
        string copy = str;
        if(copy[j] == '9'){
            copy[j] = '0';
        }else{
            copy[j] += 1;
        }
        return copy;
    }
};

int main(){
    Solution slu;
    vector<string> deadends{"0201","0101","0102","1212","2002"};
    string target = "0209";
    int ret = slu.openLock(deadends, target);
    cout << "min step to open lock: " << ret <<endl;
    return 0;
}